#include <iostream>
using namespace std;

void main ()
{
	long long int n,a,b,mod,result;
	scanf ("%I64d",&n);
	while (scanf ("%I64d%I64d%I64d",&a,&b,&mod)!=EOF)
	{
		result =1;
		while (b!=0)
		{
			if (b&1)
			{
				result *= a;
				result %= mod;
			}
			a *= a;
			a %= mod;
			b >>=1;
		}
		printf ("%I64d\n",result);
	}
}
